package com.cuz.daileetcode;

import java.util.function.DoublePredicate;

/**
 * @author cuzz
 * @version 1.0
 * @description: 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 * <p>
 * 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
 * <p>
 *  
 * 示例 1：
 * <p>
 * 输入：nums = [10,9,2,5,3,7,101,18]
 * 输出：4
 * 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
 * 示例 2：
 * <p>
 * 输入：nums = [0,1,0,3,2,3]
 * 输出：4
 * 示例 3：
 * <p>
 * 输入：nums = [7,7,7,7,7,7,7]
 * 输出：1
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 19:00 2021/9/18
 **/
public class Day1 {
    /**
     * @author cuzz
     * @version 1.0
     * @description: 动态规划
     * <p>
     * 状态转移
     * dp[i]=Max(dp[j])+1  (i！=1存在 j<i 且 arr[j]小于arr[i])
     * or
     * dp[i]=1 (i！=1存在 j<i 且 arr[j]恒大于arr[i]）||（i=1）
     * @date 19:57 2021/9/18
     **/
    public static class Solution1 {
        public static int findMaxLIS(int[] arr) {
            if (arr == null || arr.length == 0) {
                return 0;
            }
            //动态规划记录 以arr[i]结尾的最大长度
            int[] dp = new int[arr.length];
            //第一个数前面没有数设为1
            dp[0] = 1;
            //记录结果 只要不为空的数祖，最起码有一个数构成最长递增子数列
            int res = 1;
            for (int index = 1; index < arr.length; index++) {
                dp[index] = findMaxDPValueOfPre(arr, dp, index) + 1;
                res = Math.max(res, dp[index]);
            }
            return res;
        }

        /**
         * @param arr         数组
         * @param dp          动态规划记录
         * @param nowNumIndex 当前此数的位置
         * @return int 可以构成最长递增子数列数 对应的dp值
         * 此值加1 为以arr[nowNumIndex]结尾的递增子数列
         * @author cuzz
         * @description 寻找上一个结尾数小于当前数，可以构成最长递增子数列数 对应的dp值
         * 状态转移
         * @date 19:48 2021/9/18
         **/
        private static int findMaxDPValueOfPre(int[] arr, int[] dp, int nowNumIndex) {
            int res = 0;
            for (int numIndex = nowNumIndex; numIndex >= 0; numIndex--) {
                if (arr[numIndex] < arr[nowNumIndex]) {
                    res = Math.max(dp[numIndex], res);
                }
            }
            return res;
        }
    }

    /**
     * @author cuzz
     * @version 1.0
     * @description: 动态规划 + 二分 + 贪心
     * 使用二分将状态转移的寻找降低到nlogn
     * @date 20:30 2021/9/18
     **/
    public static class Solution2 {
        public static void main(String[] args) {
            int maxLIS = findMaxLIS(new int[]{0,1,0,3,2,3});
            System.out.println(maxLIS);
        }
        /**
         * @author cuzz
         * @description
         * 第一个小于num数的位置，找不到返回0 为什么是0：
         *  arr  10 9  2 5 3 7 101 18
         *  dp 0 10  0  0 0 0 0  0   0
         *  1=>9,res =1 dp[1]=9代表当前长度为1的递增子串末尾最小为9
         *  1=>2,res =1 dp[1]=2代表当前长度为1的递增子串末尾最小为2
         *  1=>5,res =2 dp[2]=2代表当前长度为2的递增子串末尾最小为5
         *  1=>3,res =2 dp[2]=3代表当前长度为2的递增子串末尾最小为3
         *  1=>7,res =3 dp[3]=7代表当前长度为2的递增子串末尾最小为7
         *   ...
         *
         *  依此类推
         * @date 23:08 2021/9/18
         **/
        public static int findMaxLIS(int[] arr) {
            if (arr == null || arr.length == 0) {
                return 0;
            }
            int res = 1;
            int[] d = new int[arr.length + 1];
            d[res] = arr[0];
            for (int index = 1; index < arr.length; index++) {
                if (arr[index] > d[res]) {
                    //如果当前数大于末尾 那么直接加入
                    //这个数和前面的数可以构成递增
                    //对应5 5>2z直接赋值
                    res++;
                    d[res] = arr[index];
                } else {
                    int left = 1;
                    int right = res;
                    //如果while 没改变pos表示 找不到 说明这个数very大 那么放在第0+1个
                    //对应 第一个数10找不到 那么ap【1】=10
                    //如果找到 单在当前位置加 表示这个数是当前递增数列最小的末尾
                    //对应3 找到5 放在2
                    int pos = 0;
                    while (left <= right) {
                        int mid = (left + right) >> 1;
                        if (d[mid] < arr[index]) {
                            pos = mid;
                            left = mid + 1;
                        } else {
                            right = mid - 1;
                        }
                    }
                    d[pos + 1] = arr[index];
                }
            }
            return res;
        }

        /**
         * @author cuzz
         * @description 找第一个大于num的数
         * @date 22:18 2021/9/18
         * @param dp 动规记录
         * @param start 起始
         * @param end 结束
         * @param num 目标
         * @return
         **/
        public static int findPreLessNum(int[] dp, int start, int end, int num) {
           int pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
            while (start <= end) {
                int mid = (start + end) >> 1;
                if (dp[mid] < num) {
                    pos = mid;
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
            return pos;
        }


    }

}
